import random as rd
import math

def JeuxAvecStrategie1(etat, n):
    fin_partie = False

    if etat in attracteurs[0]:
        partie = [("position_initiale_gagnante_J0 / J"+str(etat[1])+" commence")]
    elif etat in attracteurs[1]:
        partie = [("position_initiale_gagnante_J1 / J"+str(etat[1])+" commence")]
    else:
        partie = [("position_initiale_nulle / J"+str(etat[1])+" commence")]

    etat_ = etat
    while fin_partie == False:
        etat, type = strategie1(etat_)
        partie.append((etat_, type))

        # Vérifie si c'est un état final
        fin_partie, joueur_gagnant = partie_finie(n,etat[0])
        etat_ = etat

    partie.append((etat_, "fin partie"))

    return partie, joueur_gagnant

def JeuxAvecStrategieMiniMax(etat, n):
    fin_partie = False

    if etat in attracteurs[0]:
        partie = [("position_initiale_gagnante_J0 / J"+str(etat[1])+" commence")]
    elif etat in attracteurs[1]:
        partie = [("position_initiale_gagnante_J1 / J"+str(etat[1])+" commence")]
    else:
        partie = [("position_initiale_nulle / J"+str(etat[1])+" commence")]

    etat_ = etat
    while fin_partie == False:
        etat, type, cote = strategieMinMax(etat_)
        partie.append((etat_, type, cote))

        # Vérifie si c'est un état final
        fin_partie, joueur_gagnant = partie_finie(n,etat[0])
        etat_ = etat

    partie.append((etat_, "fin partie"))

    return partie, joueur_gagnant

def EvaluerStrategieMiniMax_heur(p,n):
    # ordre des cases : [minimax = -1, minimax = 0, minimax = 1]
    # répartition des coups choisis par l’heuristique
    # entre perdants / nuls / gagnants ;
    nbre_choix = [0, 0, 0]

    # répartition de tous les coups possibles
    # entre perdants / nuls / gagnants.
    nbre_tout  = [0, 0, 0]

    # on parcourt les états atteints après 2 coups depuis l'état initial
    for etat1 in suivants(etat_initial):
        for etat2 in suivants(etat1):
            # coups choisis par la stratégie heuristique à profondeur p
            choix = strategieMiniMax_heur(etat2, p, n)

            # comptage des vraies valeurs minimax des coups choisis
            # par l'heuristique
            for s in choix:
                nbre_choix[minimax(s) + 1] += 1

            # comptage des vraies valeurs minimax de tous les coups possibles
            for s in suivants(etat2):
                nbre_tout[minimax(s) + 1] += 1

    print("Ordre : [J1 gagne, nul, J0 gagne] = [-1, 0, 1]")
    print("Coups choisis par la stratégie heuristique :", nbre_choix)
    print("Tous les coups possibles                   :", nbre_tout)

###################################
# Chaînes gagnantes pour tests
###################################
# Cette chaîne simule une victoire de 'O' sur la ligne du milieu (cases 3, 4 et 5).
c_victoire_J0_ligne = 'X.XOOO..X'

# Ici, 'X' a réussi à aligner ses symboles sur la première colonne (cases 0, 3 et 6).
c_victoire_J1_colonne = 'XO.XO.X.O'

# Une victoire de 'O' sur la diagonale principale (cases 0, 4 et 8).
c_victoire_J0_diag = 'OX.XO..XO'

# Match Nul (Grille pleine, aucun gagnant)
c_match_nul = 'OXOOXXXOO'

# Partie en cours (Grille non pleine, aucun gagnant)
c_en_cours = 'OX..O....'

##########################################
##########################################

joueurs = {'O' : 0, 'X' : 1}
symboles = {0 : 'O', 1 : 'X'}
etat_initial = ('.'*9, 0)       #grille vide et J0 commence

# Question 1
def rangees(n):
    liste_gagnantes = []

    # Lignes
    departs_lignes = [i for i in range(0,n*n,n)]
    for depart in departs_lignes:
        liste_gagnantes.append([j for j in range(depart,depart+n)])

    # Colonnes
    for i in range(n):
        colonne = []
        for element in liste_gagnantes[0:n]:
            colonne.append(element[i])
        liste_gagnantes.append(colonne)

    # Diagonale 1
    diagonale = []
    j = 0
    for i in range(n):
        diagonale.append(liste_gagnantes[i][j])
        j = j+1
    liste_gagnantes.append(diagonale)

    # Diagonale 2
    diagonale = []
    j = n-1
    for i in range(n):
        diagonale.append(liste_gagnantes[i][j])
        j = j-1
    liste_gagnantes.append(diagonale)

    return liste_gagnantes

# Test de la question 1
print(rangees(3))

# Question 2
def partie_finie(n,c):
    # Récupère la liste des rangees gagnantes
    liste_rangees_gagnantes = rangees(n)

    # Vérifie si une des rangées gagnante se trouve dans le dictionnaire
    for rangee in liste_rangees_gagnantes:
        for joueur in ['X','O']:
            check = True
            for i in range(n):
                check = check and (c[rangee[i]] == joueur)
            if check == True:
                if joueur == 'O':
                    return (check,0)
                else:
                    return (check,1)

    # Match nul
    if "." not in c:
        return (True,None)
    else:
        return (False, None)

# Tests de la question 2
print("\nVictoire J0 (Ligne)")
print(partie_finie(3,c_victoire_J0_ligne))

print("\nVictoire J1 (Colonne)")
print(partie_finie(3,c_victoire_J1_colonne))

print("\nVictoire J0 (Diagonale)")
print(partie_finie(3,c_victoire_J0_diag))

print("\nMatch nul")
print(partie_finie(3,c_match_nul))

print("\nPartie en cours")
print(partie_finie(3,c_en_cours))



# Question 3 : creation des successeurs
def suivants(etat):
    # Récupère la grille et le joueur courant
    grille = etat[0]
    Ji = etat[1]

    # Nouveau joueur
    Jj = 1-int(Ji)

    # Construction des prochains coups possibles
    coups_possibles = []
    for indice,case in enumerate(grille):
        if case == '.':
            nouveau_coup = grille[:indice] + symboles[Ji] + grille[indice+1:]
            coups_possibles.append(tuple((nouveau_coup,Jj)))

    return coups_possibles

# Test question 3
print("\nSuccesseurs de l'état initial :")
print(suivants(etat_initial))
print("\nSuccesseurs de l'état ('OX.XOO.X.',0):")
print(suivants(('OX.XOO.X.',0)))


# Question 4 : graphe du jeu
def jeu_OXO(n,i):
    gagnants0 = []
    gagnants1 = []
    nuls = []
    etat_initial = ('.'*n**2, i)  # grille vide et Ji commence

    successeurs = {}            # Dictionnaire pour stocker les successeurs
    pile = [etat_initial]       # Pile pour stocker les états non traités
    vus = {etat_initial}

    while len(pile) != 0:
        # Récupère l'état courant
        etat_ = pile.pop()

        # Ajoute la clé si elle n'existe pas
        successeurs[etat_] = []

        # Recherche les états suivants
        etats_suivants = suivants(etat_)

        # Ajoute les états suivants dans la pile
        # et dans les listes des gagnants et des nuls
        for etat in etats_suivants:
            # Ajoute les successeurs
            successeurs[etat_].append(etat)

            # Vérifie si c'est un état final
            test = partie_finie(n,etat[0])

            # Si c'est un état final, on l'ajoute
            # aux bonnes listes
            if test[0] == True:
                successeurs[etat]=[]
                if test[1] == 0 and etat not in gagnants0:
                    gagnants0.append(etat)
                elif test[1]==1 and etat not in gagnants1:
                    gagnants1.append(etat)
                elif test[1]==None and etat not in nuls:
                    nuls.append(etat)

            # Sinon
            else:
                if etat not in vus:
                    vus.add(etat)
                    pile.append(etat)

    return successeurs, gagnants0, gagnants1, nuls

# Question 4 : autre version (donnée par un élève)
#              (il manque un test pour éviter de
#              traiter plusieurs fois un meme etat)
def jeu_OXO_v2(n,i):
    successeurs={}
    gagnant1=[]
    gagnant2=[]
    nul=[]

    dico={None:nul,0:gagnant1,1:gagnant2}
    etat=('.'*n**2, i)  # grille vide et Ji commence

    def chapeau(etat):
        successeurs[etat]=suivants(etat)

        # Vérifie si c'est un état final
        test = partie_finie(n,etat[0])

        if test[0]:
            if etat not in dico[test[1]]:
                dico[test[1]].append(etat)
        else:
            for prochain in successeurs[etat]:
                chapeau(prochain)

    chapeau(etat)
    return successeurs,gagnant1,gagnant2,nul

# Test question 4
print("\nGraphe du jeu pour n=3")
successeurs, gagnants0, gagnants1, nuls = jeu_OXO(3,0)
print("Nombre total de sommets:", len(successeurs))
print("Nombre d'états gagnants pour J0:",len(gagnants0))
print("Nombre d'états gagnants pour J1:",len(gagnants1))
print("Nombre d'états nuls:",len(nuls))

# Question 5 : Inversion dictionnaire
def inverse(dico):
    dico_inverse = {etat:[] for etat in dico}

    # Création des clés du dico inverse
    for etat in dico:
        for etat_suivant in dico[etat]:
            if etat_suivant not in dico_inverse:
                dico_inverse[etat_suivant] = []

    # Remplissage du dico inverse
    for etat in dico:
        for etat_suivant in dico[etat]:
            if etat not in dico_inverse[etat_suivant]:
                dico_inverse[etat_suivant].append(etat)
    return dico_inverse

# Test question 5
print("\nTest inversion dico pour n=2")
successeurs2, gagnants02, gagnants12, nuls2 = jeu_OXO(2,0)
print(inverse(successeurs2))

# Question 6 : Attracteur
def attracteur(joueur) :
    # Initialisation de l'attracteur
    if joueur == 0 :
        A = gagnants0[:]
    else :
        A = gagnants1[:]

    def aux(s) :
        # Récupère tous les prédecesseurs de s
        for p in predecesseurs[s] :
            # Si le prédecesseur n'a pas encore été ajouté à l'attracteur
            if p not in A :
                # Si le predécesseur est contrôlé par le joueur
                # on peut l'ajouter
                if p[1] == joueur :
                    A.append(p)
                    aux(p)
                else :
                    # Sinon, il est contrôlé par l'adversaire
                    # il faut vérfifier si tous ses successeurs
                    # arrivent dans l'attracteur avant de l'ajouter
                    convient = True
                    for sp in successeurs[p] :
                        convient = convient and sp in A
                    if convient:
                        A.append(p)
                        aux(p)

    for s in A :
        aux(s)
    return A

# Test question 6
print("\nCalcul de l'attracteur des joueurs")
predecesseurs = inverse(successeurs)
A0 = attracteur(0)
A1 = attracteur(1)
print(len(A0),len(A1))

# Question 7
def strategie1(etat):
    # Récupère le numéro du joueur Ji
    joueur = etat[1]

    # Types d'états suivants possibles
    suiv_gagnants = []
    suiv_perdants = []
    suiv_nul = []

    for position_suivant in successeurs[etat] :
        if position_suivant in attracteurs[joueur] :
            suiv_gagnants.append(position_suivant)
        elif position_suivant in attracteurs[1-joueur] :
            suiv_perdants.append(position_suivant)
        elif position_suivant in attracteurs[None] :
            suiv_nul.append(position_suivant)

    if suiv_gagnants != [] :
        return suiv_gagnants[rd.randrange(len(suiv_gagnants))], "position_gagnante"
    elif suiv_nul != [] :
        return suiv_nul[rd.randrange(len(suiv_nul))], "position_nulle"
    else:
        return suiv_perdants[rd.randrange(len(suiv_perdants))], "position_perdante"


# Question 8 : Aucune stratégie gagnante n'existe.
#              les parties donnent toujours des matchs nuls
region_nulle = [e for e in successeurs if e not in A0 and e not in A1]
attracteurs = {0:A0, 1:A1, None:region_nulle}
print("\nLance une partie")
print(JeuxAvecStrategie1(etat_initial,3))


# Question 9 : Algorithme MINIMAX
def minimax(etat):
    # MEMOISATION
    # Si la valeur a déjà été calculée
    # retourne la valeur mémorisée
    if etat in memo:
        return memo[etat]

    # CAS DES FEUILLES
    # Si c'est un état gagnant de J0
    # (feuille) ; retourne +1
    if etat in gagnants0:
        memo[etat] = 1
        return memo[etat]
    # Sinon si c'est un état gagnant de J1
    # retourne  -1
    if etat in gagnants1:
        memo[etat] = -1
        return memo[etat]
    # Sinon si c'est un match nul
    # return 0
    if etat in nuls:
        memo[etat] = 0
        return memo[etat]

    # GESTION MINMAX
    # Si c'est à J0 de jouer
    # retourne le MAX des successeurs
    if etat[1] == 0:
        vmax = -1
        for succ in successeurs[etat]:
            vmax = max(vmax, minimax(succ))
        memo[etat] = vmax
        return memo[etat]

    # Sinon retourne le min de tous
    # les successeurs
    else:
        vmin = 1
        for succ in successeurs[etat]:
            vmin = min(vmin,minimax(succ))
        memo[etat] = vmin
        return memo[etat]

# Test question 9
print("\nAlgorithme Minimax")
memo = {}
N_0 = N_1 = N_None =  0
for s in successeurs :
    if minimax(s) == 1 :
        N_0 += 1
    elif minimax(s) == -1 :
        N_1 += 1
    elif minimax(s) == 0 :
        N_None += 1
print("Nombre d'états où minimax vaut 1, -1, 0  :", N_0, N_1, N_None)

# Question 10 : pas de stratégie gagnante pour les joueurs
print("Cote de l'état initial:", minimax(etat_initial))

# Question 11
def strategieMinMax(etat):
    # Récupère le joueur
    joueur = etat[1]

    # Si J0, retourne un successeur d'une cote maximale
    if joueur == 0:
        cote = -100
        suiv_MAX = None
        for succ in successeurs[etat]:
            cote_succ = minimax(succ)
            if cote_succ > cote :
                suiv_MAX = succ
                cote = cote_succ
        return suiv_MAX, "position_MAX", cote

    # Si J1, retourne un successeur d'une cote minimale
    else:
        cote = 100
        suiv_MIN = None
        for succ in successeurs[etat]:
            cote_succ = minimax(succ)
            if cote_succ < cote :
                suiv_MIN = succ
                cote = cote_succ
        return suiv_MIN, "position_MIN", cote

# Tests de la question 11
print("MiniMax sur l'état initial (région nulle - J0 joue):",strategieMinMax(etat_initial))
print("MiniMax sur un état de A0 (J0 joue):",strategieMinMax(('.O.OXX...', 0)))
print("MiniMax sur un état de A1 (J1 joue) :",strategieMinMax(('OO.OOXX.X', 1)))
print("MiniMax sur un état de A1 (J0 joue) :",strategieMinMax(('OOX..OX.X', 0)))
print("MiniMax sur un état de A0 (J1 joue) :",strategieMinMax(('OO.X.....', 1)))

# Question11bis :
print("\nLance une partie avec stratégie MiniMax")
print(JeuxAvecStrategieMiniMax(etat_initial,3))

# Question 12: compte_lcd
def compte_lcd(grille,joueur,n):
    # Récupère les lignes / colonnes / diagonales possibles
    rangees_gagnantes = rangees(int(n))

    # Test si le joueur peut placer les pions
    nbr = 0

    for ligne in rangees_gagnantes:
        check = False
        for case in ligne:
            if symboles[1-joueur] in grille[case]:
                check = True
        if check == False:
            nbr = nbr + 1
    return nbr

# Tests question 12
print("\nTests de la fonction compte_lcd")
print("Etat initial, J0:",compte_lcd(etat_initial[0],0,3) )
print("Etat initial, J1:",compte_lcd(etat_initial[0],1,3) )
print("Grille ('XO..O....'), J0:", compte_lcd(('XO..O....'),0,3))
print("Grille ('XO..O....'), J1:", compte_lcd(('XO..O....'),1,3))
print("Grille ('X..X.....'), J0:", compte_lcd(('X..X.....'),0,3))
print("Grille ('X..X.....'), J1:", compte_lcd(('X..X.....'),1,3))


# Question 13 : Fonction heuristique
def heuristique(etat,i,n):
    # Vérifie si l'état est gagnant
    fin_partie, joueur_gagnant = partie_finie(n,etat[0])

    # Si Ji gagne
    if fin_partie == True and joueur_gagnant == i:
        return 2*n+3
    # Sinon si l'adversaire gagne
    elif fin_partie == True and joueur_gagnant == 1-i:
        return -(2*n+3)

    # Sinon calcule le nombre de possibilité de gain
    else:
        nbr_gain_i = compte_lcd(etat[0],i,n)
        nbr_gain_1_i = compte_lcd(etat[0],1-i,n)
        return nbr_gain_i-nbr_gain_1_i

# Test question 13
print("\nTests de la fonction heuristique")
print("Etat initial, J0 :",heuristique(etat_initial,0,3))
print("Etat non gagnant (('XO..O....'),0), J0:",heuristique((('XO..O....'),0),0,3))
print("Etat non gagnant (('XO..O....'),0), J1:",heuristique((('XO..O....'),0),1,3))
print("Etat gagnant pour J0 ('OXXOOXO..', 1), J0:",heuristique(('OXXOOXO..', 1),0,3))
print("Etat gagnant pour J0 ('OXXOOXO..', 1), J1:",heuristique(('OXXOOXO..', 1),1,3))

# Question 14 : Algorithme MINIMAX avec heuristique
def minimax_heur(etat,p,n):
    # Récupère le joueur
    joueur = etat[1]

    # Vérifie si c'est une feuille
    fin_partie, joueur_gagnant = partie_finie(n,etat[0])

    # Si fin de partie non nulle, retourne l'heuristique
    if fin_partie == True and joueur_gagnant != None:
        return heuristique(etat,0,n)
    # Si fin de partie nulle, retourne 0
    elif fin_partie == True and joueur_gagnant == None:
        return 0

    # Si c'est pas une feuille et p=0
    # alors renvoie l'évaluation avec l'heuristique
    if p == 0:
        return heuristique(etat,0,n)


    # GESTION MINMAX
    # Si c'est à J0 de joueur
    # retourne le MAX des successeurs
    if joueur == 0:
        vmax = -(2*n+3)
        for succ in suivants(etat):
            vmax = max(vmax, minimax_heur(succ,p-1,n))
        return vmax

    # Sinon retourne le min de tous
    # les successeurs
    else:
        vmin = +(2*n+3)
        for succ in suivants(etat):
            vmin = min(vmin,minimax_heur(succ,p-1,n))
        return vmin


# Test question 14
print("\nTests de la fonction MiniMax_heur")
print("Tests des cas terminaux")
print("J0 gagne (p=1):",minimax_heur(('OOOXX....', 1), 0, 3))
print("J0 gagne (p=4):",minimax_heur(('OOOXX....', 1), 4, 3))
print("J1 gagne (p=1)",minimax_heur(('XXXOO....', 0), 0, 3))
print("J1 gagne (p=1):",minimax_heur(('XXXOO....', 0), 4, 3))
print("Tests des coups gagnants immédiats pour J0")
print("J0 gagne en 1 coup (p=1):",minimax_heur(('OO.XX....', 0), 1, 3))
print("J0 gagne en 1 coup (p=4):",minimax_heur(('OO.XX....', 0), 4, 3))
print("Tests des coups gagnants immédiats pour J1")
print("J1 gagne en un coup (p=1):",minimax_heur(('XX.OO.O..', 1), 1, 3))
print("Coups dans l'attracteur de A0")
print("J0 gagne mais pas en un coup (p=1):",minimax_heur(('..XO.....', 0), 1, 3))
print("J0 gagne mais pas en un coup (p=4):",minimax_heur(('..XO.....', 0), 4, 3))
print("J0 gagne mais pas en un coup (p=5):",minimax_heur(('..XO.....', 0), 5, 3))
print("Coups dans l'attracteur de A1")
print("J1 gagne mais pas en un coup (p=1):",minimax_heur(('XOXO...O.', 1), 1, 3))
print("J1 gagne mais pas en un coup (p=4):",minimax_heur(('XOXO...O.', 1), 4, 3))
print("Test global depuis l'état initial:")
print("Exploration avec p=1:",minimax_heur(etat_initial, 1, 3))
print("Exploration avec p=4:",minimax_heur(etat_initial, 4, 3))
print("Exploration avec p=9:",minimax_heur(etat_initial, 9, 3))


# Question 15 : fonction strategieMiniMax_heur
def strategieMiniMax_heur(etat,p,n):
    # Récupération du joueur
    joueur = etat[1]

    # Dictionnaire pour sauvegarder les états et leurs valeurs
    # sous la forme {valeur:[états]}
    suiv_opt = {}

    # Itère les successeurs avec une profondeur p-1
    for succ in suivants(etat):
        val = minimax_heur(succ,p-1,n)
        if val not in suiv_opt:
            suiv_opt[val] = [succ]
        else:
            suiv_opt[val].append(succ)

    # Si J0 : renvoie les état MAX
    # Si J1 : renvoie les états MIN
    if joueur == 0:
        return suiv_opt[max(suiv_opt.keys())]
    else:
        return suiv_opt[min(suiv_opt.keys())]

# Test question 15
print("\nTests de la fonction strategieMinMax_heur")
print("Coup où J0 gagne immédiatement : ('OO.XX....', 0) (p=1) :",strategieMiniMax_heur(('OO.XX....', 0),1,3))
print("Coup où J1 gagne immédiatement : ('XX.OO.O..', 1) (p=1) :",strategieMiniMax_heur(('XX.OO.O..', 1),1,3))
print("Position dans l’attracteur de J0, mais sans gain immédiat  : ('..XO.....', 0) (p=1) :",strategieMiniMax_heur(('..XO.....', 0),1,3))
print("Position dans l’attracteur de J0, mais sans gain immédiat  : ('..XO.....', 0) (p=3) :",strategieMiniMax_heur(('..XO.....', 0),3,3))
print("Position dans l’attracteur de J0, mais sans gain immédiat  : ('..XO.....', 0) (p=5) :",strategieMiniMax_heur(('..XO.....', 0),5,3))
print("Position dans l’attracteur de J0, mais sans gain immédiat  : ('..XO.....', 0) (p=9) :",strategieMiniMax_heur(('..XO.....', 0),9,3))
print("Position dans l’attracteur de J1, mais sans gain immédiat  : ('O..O....X', 1) (p=1) :",strategieMiniMax_heur(('O..O....X', 1),1,3))
print("Position dans l’attracteur de J1, mais sans gain immédiat  : ('O..O....X', 1) (p=3) :",strategieMiniMax_heur(('O..O....X', 1),3,3))


# Question 16 : Evaluation de la stratégie heuristique
# Lorsque p augmente, la stratégie choisie davantage de choix qui font
# gagner J0 ; pour p=9 elle est optimale car elle descend tout l'arbre du jeu

# p=1:
# Coups choisis par la stratégie heuristique : [52, 52, 24]
# Tous les coups possibles                   : [100, 276, 128]

# p=3:
# Coups choisis par la stratégie heuristique : [32, 48, 40]
# Tous les coups possibles                   : [100, 276, 128]

# p=5:
# Coups choisis par la stratégie heuristique : [8, 52, 128]
# Tous les coups possibles                   : [100, 276, 128]

# p=9:
# Coups choisis par la stratégie heuristique : [0, 276, 128]
# Tous les coups possibles                   : [100, 276, 128]


print("\nEvaluation de la stratégie heuristique")
print("p=1:")
EvaluerStrategieMiniMax_heur(1,3)
print("p=3:")
EvaluerStrategieMiniMax_heur(3,3)
print("p=5:")
EvaluerStrategieMiniMax_heur(5,3)
print("p=9:")
EvaluerStrategieMiniMax_heur(9,3)